<!doctype html>
<html lang="en-us">
<head>

    <meta charset="utf-8">
    <meta name="generator" content="Hugo 0.59.1" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">

    <title>稀疏数组 | 林贤钦</title>
    <meta property="og:title" content="稀疏数组 - 林贤钦">
    <meta property="og:type" content="article">
        
    <meta property="article:published_time" content="2020-04-14T09:39:21&#43;08:00">
        
        
    <meta property="article:modified_time" content="2020-04-14T09:39:21&#43;08:00">
        
    <meta name="Keywords" content="java,博客,项目管理,软件架构,公众号,小程序">
    <meta name="description" content="稀疏数组">
        
    <meta name="author" content="林贤钦">
    <meta property="og:url" content="http://linxianqin.gitee.io/post/%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84/">
    <link rel="shortcut icon" href="/img/favicon.ico" type="image/x-icon">

    <link rel="stylesheet" href="/css/normalize.css">
    
        <link rel="stylesheet" href="/css/prism.css">
    
    <link rel="stylesheet" href="/css/style.css">
    <script type="text/javascript" src="//cdnjs.cloudflare.com/ajax/libs/jquery/3.4.1/jquery.min.js"></script>

    


    
    
</head>

<body>
<header id="header" class="clearfix">
	<div class="container">
        <div class="col-group">
            <div class="site-name ">
                
                    <a id="logo" href="http://linxianqin.gitee.io">
                        林贤钦
                    </a>
                
                <p class="description">专注于Java、微信小程序、移动互联网、项目管理、软件架构</p>
            </div>
            <div>
                <nav id="nav-menu" class="clearfix">
                    <a class="current" href="http://linxianqin.gitee.io">首页</a>
                    
                    <a  href="http://linxianqin.gitee.io/archives/" title="归档">归档</a>
                    
                    <a  href="http://linxianqin.gitee.io/about/" title="关于">关于</a>
                    
                </nav>
            </div>
        </div>
    </div>
</header>


<div id="body">
        
        
    <div class="container">
        <div class="col-group">

            <div class="col-8" id="main">
                <div class="res-cons">
                    <article class="post">
                        <header>
                            <h1 class="post-title">稀疏数组</h1>
                        </header>
                        <date class="post-meta meta-date">
                            2020年4月14日
                        </date>
                        
                        <div class="post-meta">
                            <span>|</span>
                            
                                <span class="meta-category"><a href="http://linxianqin.gitee.io/categories/java">java</a></span>
                            
                                <span class="meta-category"><a href="http://linxianqin.gitee.io/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84">数据结构</a></span>
                            
                        </div>
                        
                        
                        <div class="post-meta">
                            <span id="busuanzi_container_page_pv">|<span id="busuanzi_value_page_pv"></span><span> 阅读</span></span>
                        </div>
                        
                        
                        <div class="post-content">
							<nav id="TableOfContents">
<ul>
<li><a href="#1-稀疏数组">1、 稀疏数组</a>
<ul>
<li><a href="#如果这么说-还觉得很抽象-举个经典例子-五子棋">如果这么说，还觉得很抽象，举个经典例子&mdash;&gt;五子棋</a>
<ul>
<li><a href="#1-需求-编写五子棋程序-有存盘和续上盘功能-保存和取出使用io">1、需求：编写五子棋程序，有存盘和续上盘功能（保存和取出使用io）</a></li>
<li><a href="#2-把稀疏数组保存-并且可以恢复成二维数组">2、把稀疏数组保存，并且可以恢复成二维数组</a></li>
<li><a href="#3-整体分析">3、整体分析：</a>
<ul>
<li><a href="#那么我们如何将原数组转化成稀疏数组">那么我们如何将原数组转化成稀疏数组？</a>
<ul>
<li><a href="#1-暴力循环遍历原数组获取到原数组中非0的个数sum">1、暴力循环遍历原数组获取到原数组中非0的个数sum，</a></li>
<li><a href="#2-根据sum-我们可以创建稀疏数组">2、根据sum，我们可以创建稀疏数组</a></li>
<li><a href="#3-再次遍历原数组-获取原数组的非0值的行下标-列下表-值-一一赋给稀疏数组">3、再次遍历原数组，获取原数组的非0值的行下标，列下表，值，一一赋给稀疏数组</a></li>
</ul></li>
<li><a href="#如何将稀疏数组转化成原来的数组">如何将稀疏数组转化成原来的数组？</a>
<ul>
<li><a href="#1-首先先读取稀疏数组的第一行-获取原数组的行-列-值的个数-创建二维数组">1、首先先读取稀疏数组的第一行，获取原数组的行，列，值的个数，创建二维数组</a></li>
<li><a href="#2-遍历稀疏数组">2、遍历稀疏数组。</a></li>
</ul></li>
</ul></li>
</ul></li>
</ul></li>
</ul>
</nav>
                            

<h1 id="1-稀疏数组">1、 稀疏数组</h1>

<p>稀疏数组就是当数组中大部分的内容值都未被使用(或者为0),在数组中仅有少部分的空间使用，因此造成内存空间的浪费，为了节省内存空间，并不影响数组中原有的内容，我们可以使用稀疏数组去压缩数据</p>

<p>稀疏数组得处理方法是：
1) 记录二维数组 <strong>一共几行几列，有多少个不同</strong>的值
2) 把具有不同值的元素的行列及值记录在一个小规模的二维数组中，从而<strong>缩小程序的规模</strong>
3）第一行保存二维数组的行数、列数、有效值个数
4）其他行保存二维数组 有效值所在行数、列数以及值</p>

<p>如图：一共有8个值：22，15、 11、 17、 -4 、39、91、 28</p>

<p>原数组大小：6*7，那么在稀疏数组中的第一行存放数组就是这样</p>

<p>所以就有9行3列(在稀疏数组中，列是固定3)</p>

<pre><code class="language-java">int sparseArray[][] = new int[8 + 1][3];
sparseArray[0][0]=6;//原数组的行
sparseArray[0][1]=7;//原数组的列
sparseArray[0][2]=8;//原数组非0个数
</code></pre>

<p>第二行也就原数组的第一个非0数据22的存放就是：</p>

<pre><code class="language-java">sparseArray[1][0]=0;//原数组第一个非0数组的行下标
sparseArray[1][1]=3;//原数组第一个非0数组的列下标
sparseArray[1][2]=22;//原数组第一个非0数组的值
</code></pre>

<p>依次类推，可得到稀疏数组</p>

<p><img src="../img/dataStructure/sparseArray存放方式.jpg" alt="sparseArray存放方式" /></p>

<h2 id="如果这么说-还觉得很抽象-举个经典例子-五子棋">如果这么说，还觉得很抽象，举个经典例子&mdash;&gt;五子棋</h2>

<h3 id="1-需求-编写五子棋程序-有存盘和续上盘功能-保存和取出使用io">1、需求：编写五子棋程序，有存盘和续上盘功能（保存和取出使用io）</h3>

<p><img src="../imgdataStructure/sparseArray五子棋.jpg" alt="sparseArray五子棋" /></p>

<h3 id="2-把稀疏数组保存-并且可以恢复成二维数组">2、把稀疏数组保存，并且可以恢复成二维数组</h3>

<h3 id="3-整体分析">3、整体分析：</h3>

<p>在五子棋的棋谱中，我们可以看到只有两个非0值，分别在第二行的第三列和第三行的第四列，值分别为1和2。原棋盘大小11*11，即原数组大小。那么我们可以先把原数组给写出来</p>

<pre><code class="language-java">//创建一个原始数组 11*11 ---&gt;原棋盘大小
//0表示，没有棋子  1表示黑子 2表示白子
int chessArray[][] = new int[11][11];
chessArray[1][2] = 1;//第一个值的位置和值
chessArray[2][3] = 2;//第二个值的位置和值
</code></pre>

<p>根据稀疏数组的定义，我们可以先把稀疏数组写出来，然后再思考这么转化。需要的数组：有两个值：1 ，2，所以我们可以确定稀疏数组的大小【值的个数+1】【3】</p>

<pre><code class="language-java">int sparseArray[][] = new int[3][3];
</code></pre>

<p>存放数组则为：</p>

<pre><code class="language-java">sparseArray[0][0]=11;//原数组的行
sparseArray[0][1]=11;//原数组的列
sparseArray[0][2]=2;//原数组非0个数
sparseArray[1][0]=1;//值==原数组第一个的行下标
sparseArray[1][1]=2;//值==原数组第一个的列下标
sparseArray[1][2]=1;//值==原数组第一个的值
sparseArray[2][0]=2;//值==原数组第二个的行下标
sparseArray[2][1]=3;//值==原数组第二个的列下标
sparseArray[2][2]=2;//值==原数组第二个的值
</code></pre>

<h4 id="那么我们如何将原数组转化成稀疏数组">那么我们如何将原数组转化成稀疏数组？</h4>

<p>思路：</p>

<h5 id="1-暴力循环遍历原数组获取到原数组中非0的个数sum">1、暴力循环遍历原数组获取到原数组中非0的个数sum，</h5>

<pre><code class="language-java">int sum=0;
for (int[] row : chessArray) {//获取每一行
    for(int data : row){//遍历每一行的值
        //判断，如果是非0，那么sum++
        if(data!=0){
            sum++;
        }
    }
}     
</code></pre>

<h5 id="2-根据sum-我们可以创建稀疏数组">2、根据sum，我们可以创建稀疏数组</h5>

<pre><code class="language-java">int sparseArray[][] = new int [sum+1][3];
</code></pre>

<h5 id="3-再次遍历原数组-获取原数组的非0值的行下标-列下表-值-一一赋给稀疏数组">3、再次遍历原数组，获取原数组的非0值的行下标，列下表，值，一一赋给稀疏数组</h5>

<pre><code class="language-java">int count = 0;//用来记录行下标
for(int i=0;i&lt;chessArray.length;i++){
    for(int m=0;m&lt;chessArray[0].length;m++){
        //还是先判断非0
        if(chessArray[i][m]!=0){
            count++;
            sparseArray[count][0]=i;
            sparseArray[count][1]=m;
            sparseArray[count][2]=chessArray[i][m];
        }
    }
}
</code></pre>

<p>这样，我们就获取了一个稀疏数组3x9，对比原来数组11x11显然小很多。</p>

<h4 id="如何将稀疏数组转化成原来的数组">如何将稀疏数组转化成原来的数组？</h4>

<p>用上面的例子来，我们获取了一个稀疏数组</p>

<pre><code class="language-java">int sparseArray[][] = new int [9][3];
</code></pre>

<p>那么我们可以得到结果1：该原数组有8个非空值，我们可以遍历稀疏数组。</p>

<h5 id="1-首先先读取稀疏数组的第一行-获取原数组的行-列-值的个数-创建二维数组">1、首先先读取稀疏数组的第一行，获取原数组的行，列，值的个数，创建二维数组</h5>

<pre><code class="language-java">//1.读取稀疏数组第一行数据 创建二维数组
int chessArray2[][] = new int[sparseArray[0][0]][sparseArray[0][1]];
</code></pre>

<h5 id="2-遍历稀疏数组">2、遍历稀疏数组。</h5>

<pre><code class="language-java">for(int i=1;i&lt;sparseArray.length;i++){
	chessArray2[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
}
</code></pre>

                        </div>
						 
                        
<div class="post-archive">
    <ul class="post-copyright">
        <li><strong>原文作者：</strong><a rel="author" href="http://linxianqin.gitee.io">林贤钦</a></li>
        <li style="word-break:break-all"><strong>原文链接：</strong><a href="http://linxianqin.gitee.io/post/%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84/">http://linxianqin.gitee.io/post/%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84/</a></li>
        <li><strong>版权声明：</strong>本作品采用<a rel="license" href="https://linxianqin.gitee.io">知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议</a>进行许可，非商业转载请注明出处（作者，原文链接），商业转载请联系作者获得授权。</li>
    </ul>
</div>
<br/>



                        

<div class="post-archive">
    <h2>See Also</h2>
    <ul class="listing">
        
        <li><a href="/post/%E9%98%BF%E9%87%8C%E4%BA%91EasyExcel%E5%AE%9E%E7%8E%B0%E5%90%8E%E7%AB%AF%E5%AF%B9Excel%E7%9A%84%E8%AF%BB%E5%86%99%E6%93%8D%E4%BD%9C/">使用阿里云EasyExcel实现后端对Excel的读写操作</a></li>
        
        <li><a href="/post/%E9%98%BF%E9%87%8C%E4%BA%91oss%E5%AF%B9%E8%B1%A1%E5%AD%98%E5%82%A8%E6%9C%8D%E5%8A%A1%E5%AE%9E%E7%8E%B0/">阿里云oss对象存储服务实现</a></li>
        
        <li><a href="/post/%E6%B5%85%E8%B0%88springboot-Security-Jwt-%E5%AE%9E%E7%8E%B0token/">springBoot&#43;Security&#43;JWT&#43;Jpa&#43;Vue实现登录权限控制</a></li>
        
        <li><a href="/post/springSecurity%E7%9A%84session%E7%AE%A1%E7%90%86%E5%8F%8A%E5%AE%89%E5%85%A8%E9%85%8D%E7%BD%AE/">SpringSecurity的session管理及安全配置</a></li>
        
        <li><a href="/post/springSecurity%E8%87%AA%E5%AE%9A%E4%B9%89%E8%AE%A4%E8%AF%81%E7%BB%93%E6%9E%9C%E5%A4%84%E7%90%86/">SpringSecurity自定义认证结果处理</a></li>
        
    </ul>
</div>


                        <div class="post-meta meta-tags">
                            
                            <ul class="clearfix">
                                
                                <li><a href="http://linxianqin.gitee.io/tags/java">java</a></li>
                                
                                <li><a href="http://linxianqin.gitee.io/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84">数据结构</a></li>
                                
                            </ul>
                            
                        </div>
                    </article>
                    
    

    
    
    <div class="post bg-white">
      <script src="https://utteranc.es/client.js"
            repo= "757610938/hugo-blogs-utterances"
            issue-term="pathname"
            theme="github-light"
            crossorigin="anonymous"
            async>
      </script>
    </div>
    
                </div>
            </div>
            <div id="secondary">
    <section class="widget">
        <form id="search" action="//www.google.com/search" method="get" accept-charset="utf-8" target="_blank" _lpchecked="1">
      
      <input type="text" name="q" maxlength="20" placeholder="Search">
      <input type="hidden" name="sitesearch" value="http://linxianqin.gitee.io">
      <button type="submit" class="submit icon-search"></button>
</form>
    </section>
    
    <section class="widget">
        <h3 class="widget-title">最近文章</h3>
<ul class="widget-list">
    
    <li>
        <a href="http://linxianqin.gitee.io/post/java-%E5%8F%8D%E5%B0%84/" title="Java 反射">Java 反射</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/java-%E9%93%BE%E8%A1%A8/" title="Java 链表">Java 链表</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E7%9F%AD%E4%BF%A1%E6%B3%A8%E5%86%8C%E5%92%8C%E5%BE%AE%E4%BF%A1%E7%99%BB%E5%BD%95%E7%9A%84%E5%AE%9E%E7%8E%B0/" title="短信注册和微信登录的实现">短信注册和微信登录的实现</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/OAuth2.0%E8%AE%A4%E8%AF%81%E6%8E%88%E6%9D%83%E5%8D%95%E7%82%B9%E7%99%BB%E5%BD%95/" title="OAuth2.0认证授权单点登录">OAuth2.0认证授权单点登录</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/Nacos%E6%9C%8D%E5%8A%A1%E6%B3%A8%E5%86%8C%E4%B8%AD%E5%BF%83/" title="Nacos服务注册中心">Nacos服务注册中心</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/SpringCloud%E5%BE%AE%E6%9C%8D%E5%8A%A1/" title="SpringCloud微服务">SpringCloud微服务</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E9%98%BF%E9%87%8C%E4%BA%91%E8%A7%86%E9%A2%91%E7%82%B9%E6%92%AD%E6%9C%8D%E5%8A%A1/" title="阿里云视频点播服务前后端实现">阿里云视频点播服务前后端实现</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E9%98%9F%E5%88%97/" title="队列">队列</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E7%A8%80%E7%96%8F%E6%95%B0%E7%BB%84/" title="稀疏数组">稀疏数组</a>
    </li>
    
    <li>
        <a href="http://linxianqin.gitee.io/post/%E9%98%BF%E9%87%8C%E4%BA%91EasyExcel%E5%AE%9E%E7%8E%B0%E5%90%8E%E7%AB%AF%E5%AF%B9Excel%E7%9A%84%E8%AF%BB%E5%86%99%E6%93%8D%E4%BD%9C/" title="使用阿里云EasyExcel实现后端对Excel的读写操作">使用阿里云EasyExcel实现后端对Excel的读写操作</a>
    </li>
    
</ul>
    </section>

    

    <section class="widget">
        <h3 class="widget-title">分类</h3>
<ul class="widget-list">
    
    <li><a href="http://linxianqin.gitee.io/categories/JWT/">JWT (2)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/hugo/">hugo (2)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/java/">java (18)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/java8/">java8 (1)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/springCloud/">springCloud (2)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/springSecurity/">springSecurity (4)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/vue/">vue (5)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/yml/">yml (1)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构 (3)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/%E8%BD%AF%E4%BB%B6%E6%B5%8B%E8%AF%95/">软件测试 (1)</a></li>
    
    <li><a href="http://linxianqin.gitee.io/categories/%E9%98%BF%E9%87%8C%E4%BA%91/">阿里云 (4)</a></li>
    
</ul>
    </section>

    <section class="widget">
        <h3 class="widget-title">标签</h3>
<div class="tagcloud">
    
    <a href="http://linxianqin.gitee.io/tags/JWT/">JWT</a>
    
    <a href="http://linxianqin.gitee.io/tags/hugo/">hugo</a>
    
    <a href="http://linxianqin.gitee.io/tags/java/">java</a>
    
    <a href="http://linxianqin.gitee.io/tags/java8/">java8</a>
    
    <a href="http://linxianqin.gitee.io/tags/spring/">spring</a>
    
    <a href="http://linxianqin.gitee.io/tags/springBoot/">springBoot</a>
    
    <a href="http://linxianqin.gitee.io/tags/springCloud/">springCloud</a>
    
    <a href="http://linxianqin.gitee.io/tags/ssm/">ssm</a>
    
    <a href="http://linxianqin.gitee.io/tags/vue/">vue</a>
    
    <a href="http://linxianqin.gitee.io/tags/yml/">yml</a>
    
    <a href="http://linxianqin.gitee.io/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a>
    
    <a href="http://linxianqin.gitee.io/tags/%E8%BD%AF%E4%BB%B6%E6%B5%8B%E8%AF%95/">软件测试</a>
    
    <a href="http://linxianqin.gitee.io/tags/%E9%98%BF%E9%87%8C%E4%BA%91/">阿里云</a>
    
</div>
    </section>

    
<section class="widget">
    <h3 class="widget-title">友情链接</h3>
    <ul class="widget-list">
        
        <li>
            <a target="_blank" href="https://www.cnki.net" title="中国知网">中国知网</a>
        </li>
        
        <li>
            <a target="_blank" href="https://linxianqin.com" title="个人的另一个博客网站(国内加载慢)">个人的另一个博客网站(国内加载慢)</a>
        </li>
        
    </ul>
</section>


    <section class="widget">
        <h3 class="widget-title">其它</h3>
        <ul class="widget-list">
            <li><a href="http://linxianqin.gitee.io/index.xml">文章 RSS</a></li>
        </ul>
    </section>
</div>
        </div>
    </div>
</div>
<footer id="footer">
    <div class="container">
        &copy; 2020 <a href="http://linxianqin.gitee.io">林贤钦 By 林贤钦</a>.
        Powered by <a rel="nofollow noreferer noopener" href="https://gohugo.io" target="_blank">Hugo</a>.
        <a href="https://www.flysnow.org/" target="_blank">Theme</a> based on <a href="https://github.com/rujews/maupassant-hugo" target="_blank">maupassant</a>.
        
    </div>
</footer>


    
    <script type="text/javascript">
        
        (function () {
            $("pre code").parent().addClass("line-numbers")
        }());

        window.MathJax = {
            tex2jax: {
                inlineMath: [['$', '$']],
                processEscapes: true
                }
            };
    </script>
    <script type="text/javascript" src="/js/prism.js" async="true"></script>
    <script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>


<a id="rocket" href="#top"></a>
<script type="text/javascript" src="/js/totop.js?v=0.0.0" async=""></script>

<script type="application/javascript">
var doNotTrack = false;
if (!doNotTrack) {
	window.ga=window.ga||function(){(ga.q=ga.q||[]).push(arguments)};ga.l=+new Date;
	ga('create', 'GA ID', 'auto');
	
	ga('send', 'pageview');
}
</script>
<script async src='https://www.google-analytics.com/analytics.js'></script>



    <script type="text/javascript" src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" async></script>




</body>
</html>
